package com.srunpass.algorithm;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @author srunpass
 * @version Id: 俄罗斯套娃信封问题, v 0.1 2024/7/4 17:58 srunpass Exp $
 */
public class 俄罗斯套娃信封问题 {

    public static void main(String[] args) {
        俄罗斯套娃信封问题 res = new 俄罗斯套娃信封问题();
        int[][] e = {{15,8},{2,20},{2,14},{4,17},{8,19},{8,9},{5,7},{11,19},{8,11},{13,11},{2,13},{11,19},{8,11},{13,11},{2,13},{11,19},{16,1},{18,13},{14,17},{18,19}};
        System.out.println(res.maxEnvelopes(e));
    }

    Integer[] res;
    int len;
    int[][] envelopes;

    public int maxEnvelopes(int[][] envelopes) {
        this.envelopes = envelopes;
        len = envelopes.length;
        res = new Integer[len];
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) {
                    return e1[0] - e2[0];
                } else {
                    return e2[1] - e1[1];
                }
            }
        });
        int site = 0;
        res[0] = envelopes[0][1];
        for (int i = 1; i < len; i++) {
            if (envelopes[i][1] > res[site]) {
                res[++site] = envelopes[i][1];
            } else {
                int index = findIndex(0, site + 1, envelopes[i][1]);
                res[index] = envelopes[i][1];
            }
        }
        return site + 1;
    }

    int findIndex(int l, int r, int target) {
        if (l == r) {
            return r;
        }
        int mid = (l + r) / 2;
        if (res[mid] < target) {
            return findIndex(mid + 1, r, target);

        } else  {
            return findIndex(l, mid, target);

        }
    }


}
